// 93. 复原IP地址
// https://leetcode.cn/problems/restore-ip-addresses/

/**
示例 1：

输入：s = "25525511135"
输出：["255.255.11.135","255.255.111.35"]
示例 2：

输入：s = "0000"
输出：["0.0.0.0"]
示例 3：

输入：s = "101023"
输出：["1.0.10.23","1.0.102.3","10.1.0.23","10.10.2.3","101.0.2.3"]
 */

/**
 * @param {string} s
 * @return {string[]}
 */
var restoreIpAddresses = function (s) {
    let strArr = s.split('');
    const combDots = combinationDots(s.length - 1);

    let ips = [];
    for (let i = 0; i < combDots.length; i++) {
        let curDotComb = combDots[i];
        const d1 = curDotComb[0];
        const d2 = curDotComb[1];
        const d3 = curDotComb[2];

        if (
            d1 >= 4 ||
            d2 - d1 >= 4 ||
            d3 - d2 >= 4 ||
            strArr.length - d3 >= 4
        ) {
            continue;
        }

        let newIPArr = [].concat(strArr);
        newIPArr.splice(d3, 0, '.');
        newIPArr.splice(d2, 0, '.');
        newIPArr.splice(d1, 0, '.');

        const newIP = newIPArr.join('');
        if (isIP(newIP)) {
            ips.push(newIP);
        }
    }

    console.log(JSON.stringify(ips));
    return ips;
};

function isIP(strIP) {
    let regex =
        /^((\d|[1-9]\d|1\d{2}|2[0-4]\d|25[0-5])\.){3}(\d|[1-9]\d|1\d{2}|2[0-4]\d|25[0-5])$/;
    return regex.test(strIP);
}

function combinationDots(nums) {
    let arr = new Array(nums).fill(1).map((_, i) => i + 1);
    let dotsArr = generateAllCombination(arr, 3);
    return dotsArr;
}

function generateAllCombination(arr, max) {
    arr.sort((a, b) => a - b);

    let ret = [];

    for (let i = 0; i < arr.length; i++) {
        dfs(arr, max, i, 0, [], ret);
    }

    return ret;
}

function dfs(arr, max, index, level, acc, all) {
    if (acc.length == max || index + level >= arr.length) {
        return;
    }

    acc.push(arr[level + index]);

    for (let i = index; i < arr.length; i++) {
        let newAcc = JSON.parse(JSON.stringify(acc));
        if (level + 1 == max) {
            all.push(acc);
            break;
        }
        dfs(arr, max, i, level + 1, newAcc, all);
    }
}

// "25525511135"
restoreIpAddresses('25525511135');

// 25.525.511.135
// 255.25.511.135
// 255.255.11.135
// 255.255.111.35
